/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.cf.code;

import java.util.ArrayList;

import com.android.dx.rop.cst.Constant;
import com.android.dx.rop.cst.CstMemberRef;
import com.android.dx.rop.cst.CstString;
import com.android.dx.rop.cst.CstType;
import com.android.dx.rop.type.Type;
import com.android.dx.util.Bits;
import com.android.dx.util.IntList;

/**
 * Utility that identifies basic blocks in bytecode.
 */
public final class BasicBlocker implements BytecodeArray.Visitor {

	/** {@code non-null;} method being converted */
	private final ConcreteMethod method;

	/**
	 * {@code non-null;} work set; bits indicate offsets in need of examination
	 */
	private final int[] workSet;

	/**
	 * {@code non-null;} live set; bits indicate potentially-live opcodes;
	 * contrawise, a bit that isn't on is either in the middle of an instruction
	 * or is a definitely-dead opcode
	 */
	private final int[] liveSet;

	/**
	 * {@code non-null;} block start set; bits indicate the starts of basic
	 * blocks, including the opcodes that start blocks of definitely-dead code
	 */
	private final int[] blockSet;

	/**
	 * {@code non-null, sparse;} for each instruction offset to a branch of some
	 * sort, the list of targets for that instruction
	 */
	private final IntList[] targetLists;

	/**
	 * {@code non-null, sparse;} for each instruction offset to a throwing
	 * instruction, the list of exception handlers for that instruction
	 */
	private final ByteCatchList[] catchLists;

	/** offset of the previously parsed bytecode */
	private int previousOffset;

	/**
	 * Identifies and enumerates the basic blocks in the given method, returning
	 * a list of them. The returned list notably omits any definitely-dead code
	 * that is identified in the process.
	 * 
	 * @param method
	 *            {@code non-null;} method to convert
	 * @return {@code non-null;} list of basic blocks
	 */
	public static ByteBlockList identifyBlocks(ConcreteMethod method) {
		BasicBlocker bb = new BasicBlocker(method);

		bb.doit();
		return bb.getBlockList();
	}

	/**
	 * Constructs an instance. This class is not publicly instantiable; use
	 * {@link #identifyBlocks}.
	 * 
	 * @param method
	 *            {@code non-null;} method to convert
	 */
	private BasicBlocker(ConcreteMethod method) {
		if (method == null) {
			throw new NullPointerException("method == null");
		}

		this.method = method;

		/*
		 * The "+1" below is so the idx-past-end is also valid, avoiding a
		 * special case, but without preventing flow-of-control falling past the
		 * end of the method from getting properly reported.
		 */
		int sz = method.getCode().size() + 1;

		workSet = Bits.makeBitSet(sz);
		liveSet = Bits.makeBitSet(sz);
		blockSet = Bits.makeBitSet(sz);
		targetLists = new IntList[sz];
		catchLists = new ByteCatchList[sz];
		previousOffset = -1;
	}

	/*
	 * Note: These methods are defined implementation of the interface
	 * BytecodeArray.Visitor; since the class isn't publicly instantiable, no
	 * external code ever gets a chance to actually call these methods.
	 */

	/** {@inheritDoc} */
	public void visitInvalid(int opcode, int offset, int length) {
		visitCommon(offset, length, true);
	}

	/** {@inheritDoc} */
	public void visitNoArgs(int opcode, int offset, int length, Type type) {
		switch (opcode) {
		case ByteOps.IRETURN:
		case ByteOps.RETURN: {
			visitCommon(offset, length, false);
			targetLists[offset] = IntList.EMPTY;
			break;
		}
		case ByteOps.ATHROW: {
			visitCommon(offset, length, false);
			visitThrowing(offset, length, false);
			break;
		}
		case ByteOps.IALOAD:
		case ByteOps.LALOAD:
		case ByteOps.FALOAD:
		case ByteOps.DALOAD:
		case ByteOps.AALOAD:
		case ByteOps.BALOAD:
		case ByteOps.CALOAD:
		case ByteOps.SALOAD:
		case ByteOps.IASTORE:
		case ByteOps.LASTORE:
		case ByteOps.FASTORE:
		case ByteOps.DASTORE:
		case ByteOps.AASTORE:
		case ByteOps.BASTORE:
		case ByteOps.CASTORE:
		case ByteOps.SASTORE:
		case ByteOps.ARRAYLENGTH:
		case ByteOps.MONITORENTER:
		case ByteOps.MONITOREXIT: {
			/*
			 * These instructions can all throw, so they have to end the block
			 * they appear in (since throws are branches).
			 */
			visitCommon(offset, length, true);
			visitThrowing(offset, length, true);
			break;
		}
		case ByteOps.IDIV:
		case ByteOps.IREM: {
			/*
			 * The int and long versions of division and remainder may throw,
			 * but not the other types.
			 */
			visitCommon(offset, length, true);
			if ((type == Type.INT) || (type == Type.LONG)) {
				visitThrowing(offset, length, true);
			}
			break;
		}
		default: {
			visitCommon(offset, length, true);
			break;
		}
		}
	}

	/** {@inheritDoc} */
	public void visitLocal(int opcode, int offset, int length, int idx,
			Type type, int value) {
		if (opcode == ByteOps.RET) {
			visitCommon(offset, length, false);
			targetLists[offset] = IntList.EMPTY;
		} else {
			visitCommon(offset, length, true);
		}
	}

	/** {@inheritDoc} */
	public void visitConstant(int opcode, int offset, int length, Constant cst,
			int value) {
		visitCommon(offset, length, true);

		if ((cst instanceof CstMemberRef) || (cst instanceof CstType)
				|| (cst instanceof CstString)) {
			/*
			 * Instructions with these sorts of constants have the possibility
			 * of throwing, so this instruction needs to end its block (since it
			 * can throw, and possible-throws are branch points).
			 */
			visitThrowing(offset, length, true);
		}
	}

	/** {@inheritDoc} */
	public void visitBranch(int opcode, int offset, int length, int target) {
		switch (opcode) {
		case ByteOps.GOTO: {
			visitCommon(offset, length, false);
			targetLists[offset] = IntList.makeImmutable(target);
			break;
		}
		case ByteOps.JSR: {
			/*
			 * Each jsr is quarantined into a separate block (containing only
			 * the jsr instruction) but is otherwise treated as a conditional
			 * branch. (That is to say, both its target and next instruction
			 * begin new blocks.)
			 */
			addWorkIfNecessary(offset, true);
			// Fall through to next case...
		}
		default: {
			int next = offset + length;
			visitCommon(offset, length, true);
			addWorkIfNecessary(next, true);
			targetLists[offset] = IntList.makeImmutable(next, target);
			break;
		}
		}

		addWorkIfNecessary(target, true);
	}

	/** {@inheritDoc} */
	public void visitSwitch(int opcode, int offset, int length,
			SwitchList cases, int padding) {
		visitCommon(offset, length, false);
		addWorkIfNecessary(cases.getDefaultTarget(), true);

		int sz = cases.size();
		for (int i = 0; i < sz; i++) {
			addWorkIfNecessary(cases.getTarget(i), true);
		}

		targetLists[offset] = cases.getTargets();
	}

	/** {@inheritDoc} */
	public void visitNewarray(int offset, int length, CstType type,
			ArrayList<Constant> intVals) {
		visitCommon(offset, length, true);
		visitThrowing(offset, length, true);
	}

	/**
	 * Extracts the list of basic blocks from the bit sets.
	 * 
	 * @return {@code non-null;} the list of basic blocks
	 */
	private ByteBlockList getBlockList() {
		BytecodeArray bytes = method.getCode();
		ByteBlock[] bbs = new ByteBlock[bytes.size()];
		int count = 0;

		for (int at = 0, next; /* at */; at = next) {
			next = Bits.findFirst(blockSet, at + 1);
			if (next < 0) {
				break;
			}

			if (Bits.get(liveSet, at)) {
				/*
				 * Search backward for the branch or throwing instruction at the
				 * end of this block, if any. If there isn't any, then "next" is
				 * the sole target.
				 */
				IntList targets = null;
				int targetsAt = -1;
				ByteCatchList blockCatches;

				for (int i = next - 1; i >= at; i--) {
					targets = targetLists[i];
					if (targets != null) {
						targetsAt = i;
						break;
					}
				}

				if (targets == null) {
					targets = IntList.makeImmutable(next);
					blockCatches = ByteCatchList.EMPTY;
				} else {
					blockCatches = catchLists[targetsAt];
					if (blockCatches == null) {
						blockCatches = ByteCatchList.EMPTY;
					}
				}

				bbs[count] = new ByteBlock(at, at, next, targets, blockCatches);
				count++;
			}
		}

		ByteBlockList result = new ByteBlockList(count);
		for (int i = 0; i < count; i++) {
			result.set(i, bbs[i]);
		}

		return result;
	}

	/**
	 * Does basic block identification.
	 */
	private void doit() {
		BytecodeArray bytes = method.getCode();
		ByteCatchList catches = method.getCatches();
		int catchSz = catches.size();

		/*
		 * Start by setting offset 0 as the start of a block and in need of
		 * work...
		 */
		Bits.set(workSet, 0);
		Bits.set(blockSet, 0);

		/*
		 * And then process the work set, add new work based on exception ranges
		 * that are active, and iterate until there's nothing left to work on.
		 */
		while (!Bits.isEmpty(workSet)) {
			try {
				bytes.processWorkSet(workSet, this);
			} catch (IllegalArgumentException ex) {
				// Translate the exception.
				throw new SimException("flow of control falls off "
						+ "end of method", ex);
			}

			for (int i = 0; i < catchSz; i++) {
				ByteCatchList.Item item = catches.get(i);
				int start = item.getStartPc();
				int end = item.getEndPc();
				if (Bits.anyInRange(liveSet, start, end)) {
					Bits.set(blockSet, start);
					Bits.set(blockSet, end);
					addWorkIfNecessary(item.getHandlerPc(), true);
				}
			}
		}
	}

	/**
	 * Sets a bit in the work set, but only if the instruction in question isn't
	 * yet known to be possibly-live.
	 * 
	 * @param offset
	 *            offset to the instruction in question
	 * @param blockStart
	 *            {@code true} iff this instruction starts a basic block
	 */
	private void addWorkIfNecessary(int offset, boolean blockStart) {
		if (!Bits.get(liveSet, offset)) {
			Bits.set(workSet, offset);
		}

		if (blockStart) {
			Bits.set(blockSet, offset);
		}
	}

	/**
	 * Helper method used by all the visitor methods.
	 * 
	 * @param offset
	 *            offset to the instruction
	 * @param length
	 *            length of the instruction, in bytes
	 * @param nextIsLive
	 *            {@code true} iff the instruction after the indicated one is
	 *            possibly-live (because this one isn't an unconditional branch,
	 *            a return, or a switch)
	 */
	private void visitCommon(int offset, int length, boolean nextIsLive) {
		Bits.set(liveSet, offset);

		if (nextIsLive) {
			/*
			 * If the next instruction is flowed to by this one, just add it to
			 * the work set, and then a subsequent visit*() will deal with it as
			 * appropriate.
			 */
			addWorkIfNecessary(offset + length, false);
		} else {
			/*
			 * If the next instruction isn't flowed to by this one, then mark it
			 * as a start of a block but *don't* add it to the work set, so that
			 * in the final phase we can know dead code blocks as those marked
			 * as blocks but not also marked live.
			 */
			Bits.set(blockSet, offset + length);
		}
	}

	/**
	 * Helper method used by all the visitor methods that deal with opcodes that
	 * possibly throw. This method should be called after calling
	 * {@link #visitCommon}.
	 * 
	 * @param offset
	 *            offset to the instruction
	 * @param length
	 *            length of the instruction, in bytes
	 * @param nextIsLive
	 *            {@code true} iff the instruction after the indicated one is
	 *            possibly-live (because this one isn't an unconditional throw)
	 */
	private void visitThrowing(int offset, int length, boolean nextIsLive) {
		int next = offset + length;

		if (nextIsLive) {
			addWorkIfNecessary(next, true);
		}

		ByteCatchList catches = method.getCatches().listFor(offset);
		catchLists[offset] = catches;
		targetLists[offset] = catches.toTargetList(nextIsLive ? next : -1);
	}

	/**
	 * {@inheritDoc}
	 */
	public void setPreviousOffset(int offset) {
		previousOffset = offset;
	}

	/**
	 * {@inheritDoc}
	 */
	public int getPreviousOffset() {
		return previousOffset;
	}
}
